package com.yubest;

import java.util.Arrays;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
 * <p>
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * <p>
 * 必须 原地 修改，只允许使用额外常数空间。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 * 示例 2：
 * <p>
 * 输入：nums = [3,2,1]
 * 输出：[1,2,3]
 * 示例 3：
 * <p>
 * 输入：nums = [1,1,5]
 * 输出：[1,5,1]
 * 示例 4：
 * <p>
 * 输入：nums = [1]
 * 输出：[1]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 100
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/4 17:22
 */
public class P0031 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        new Solution31().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

        nums = new int[]{3, 2, 1};
        new Solution31().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

        nums = new int[]{1, 1, 5};
        new Solution31().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

        nums = new int[]{1};
        new Solution31().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

        nums = new int[]{1, 2, 3, 4, 8, 1, 2};
        new Solution31().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

        nums = new int[]{1, 2, 4, 3, 1};
        new Solution31().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));

        nums = new int[]{4, 2, 2, 1};
        new Solution31().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}

class Solution31 {

    /**
     * 思路：两遍扫描
     *
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        int t, p = 0;
        boolean isFind = false;
        for (int i = nums.length - 2; i >= 0; i--) {
            //找到第一个降序的元素
            if (!isFind && nums[i] < nums[i + 1]) {
                p = i + 1;
                //从右往左遍历
                for (int j = nums.length - 1; j > i; j--) {
                    //找到第一个大于num[i]的数
                    if (nums[i] < nums[j]) {
                        t = nums[i];
                        nums[i] = nums[j];
                        nums[j] = t;
                        isFind = true;
                        break;
                    }
                }
            }
        }
        //将p之后的元素重新按小到大排序
        for (int i = nums.length - 1; i > p; i--, p++) {
            //因为p到nums.length - 1必定为降序
            t = nums[i];
            nums[i] = nums[p];
            nums[p] = t;
        }
    }
}
